package com.yangzhe.algorithm.c043;

// 现在有一个打怪类型的游戏，这个游戏是这样的，你有n个技能
// 每一个技能会有一个伤害，
// 同时若怪物小于等于一定的血量，则该技能可能造成双倍伤害
// 每一个技能最多只能释放一次，已知怪物有m点血量
// 现在想问你最少用几个技能能消灭掉他(血量小于等于0)
// 技能的数量是n，怪物的血量是m
// i号技能的伤害是x[i]，i号技能触发双倍伤害的血量最小值是y[i]
// 1 <= n <= 10
// 1 <= m、x[i]、y[i] <= 10^6
// 测试链接 : https://www.nowcoder.com/practice/d88ef50f8dab4850be8cd4b95514bbbd
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"
// 可以直接通过

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Code01_KillMonsterEverySkillUseOnce {
    public static int MAX_N = 11;

    /**
     * 技能伤害数组
     */
    public static int damages[] = new int[MAX_N];

    /**
     * 技能血量阈值数组
     */
    public static int thresholds[] = new int[MAX_N];

    /**
     * java计算量在10^7/10^8是1s左右，而og平台判断超时大概就是这个计算量
     * 如果使用10个技能 使用、不使用 全排列，复杂度 10!，计算量是 10^6，小于 10^7/10^8，按照这个推断直接用全排列算法即可
     *
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        List<Integer> result = new ArrayList<>();
        try (InputStreamReader intput = new InputStreamReader(System.in);
             BufferedReader bufferedReader = new BufferedReader(intput);
        ) {
            StreamTokenizer tokenizer = new StreamTokenizer(bufferedReader);
            // 测试数据组数
            tokenizer.nextToken();
            int testGroupCount = (int) tokenizer.nval;

            for (int groupCount = 0; groupCount < testGroupCount; groupCount++) {
                // 当前组技能量
                tokenizer.nextToken();
                int skillCount = (int) tokenizer.nval;

                // 当前组怪物血量
                tokenizer.nextToken();
                int monsterHealth = (int) tokenizer.nval;

                for (int j = 0; j < skillCount; j++) {
                    tokenizer.nextToken();
                    damages[j] = (int) tokenizer.nval;

                    tokenizer.nextToken();
                    thresholds[j] = (int) tokenizer.nval;
                }
                int count = f(monsterHealth, 0, skillCount);
                result.add(count == Integer.MAX_VALUE ? -1 : count);
            }
        }

        try (OutputStreamWriter writer = new OutputStreamWriter(System.out);
             PrintWriter print = new PrintWriter(writer)
        ) {
            for (Integer i : result) {
                print.println(i);
            }
        }
    }

    public static int f(int monsterHealth, int i, int skillCount) {
        // 如果上一次的技能已经上怪物死了，则当前位置就是已经使用的技能数量
        if (monsterHealth < 0) {
            return i;
        }

        // 如果技能都用完了，说明是无效的答案
        if (i > skillCount) {
            return Integer.MAX_VALUE;
        }

        // 038全排列代码
        int result = Integer.MAX_VALUE;
        for (int j = i; j < skillCount; j++) {
            // 从i位置挨个尝试技能
            swap(i, j);

            // 题目描述主干低于，按理解应该是<,但后面又解释说明是<=
            int damage = monsterHealth <= thresholds[i] ? damages[i] * 2 : damages[i];
            int tryResult = f(monsterHealth - damage, i + 1, skillCount);
            // 取结果最小的
            result = Math.min(tryResult, result);
            // 试完了，换回来
            swap(i, j);
        }

        return result;
    }

    /**
     * 交换两个技能位置
     *
     * @param i
     * @param j
     */
    public static void swap(int i, int j) {
        int damage = damages[i];
        damages[i] = damages[j];
        damages[j] = damage;

        int threshold = thresholds[i];
        thresholds[i] = thresholds[j];
        thresholds[j] = threshold;
    }

}